package com.zhugang.week08;

/**
 * @program algorithms
 * @description: solveSudoku
 * @author: chanzhugang
 * @create: 2022/08/04 16:38
 */
public class SolveSudoku {

    /**
     * 37 解数独
     *
     * @param board
     */
    // 定义数字是否在行、列、九宫格里存在
    private boolean[][] rows = new boolean[9][10];
    private boolean[][] cols = new boolean[9][10];
    private boolean[][][] blocks = new boolean[3][3][10];
    private boolean solved = false;

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    // 此数字出现过
                    rows[i][num] = true;
                    cols[j][num] = true;
                    blocks[i / 3][j / 3][num] = true;
                }

            }
        }
        backtrack(0, 0, board);
    }

    private void backtrack(int row, int col, char[][] board) {
        if (solved) return;
        if (row == 9) {
            solved = true;
            return;
        }

        if (board[row][col] != '.') {
            // 跳下个阶段
            int nextRow = row;
            int nextCol = col + 1;
            if (col == 8) {
                // 跳下一行坐标
                nextRow = row + 1;
                nextCol = 0;
            }
            backtrack(nextRow, nextCol, board);
            if (solved) {
                return;
            }
        } else {
            for (int num = 1; num <= 9; num++) {
                if (!rows[row][num] && !cols[col][num] && !blocks[row / 3][col / 3][num]) {
                    //数字转成字符， 数字没出现过
                    board[row][col] = String.valueOf(num).charAt(0);
                    rows[row][num] = true;
                    cols[col][num] = true;
                    blocks[row / 3][col / 3][num] = true;
                    int nextRow = row;
                    int nextCol = col + 1;
                    if (col == 8) {
                        nextRow = row + 1;
                        nextCol = 0;
                    }
                    // 下个阶段回溯
                    backtrack(nextRow, nextCol, board);
                    if (solved) {
                        return;
                    }
                    board[row][col] = '.';
                    rows[row][num] = false;
                    cols[col][num] = false;
                    blocks[row / 3][col / 3][num] = false;
                }
            }
        }
    }


}